\chapter{数论}

\section{最大公约数 / 最小公倍数}

\subsection{最大公约数（GCD, Greatest Common Divisor）}

两个整数$ a $和$ b $的最大公约数$ gcd(a, b) $为能够同时整除$ a $和$ b $的最大整数。\\

例如：

\begin{itemize}
    \item $ gcd(24, 36) = 12 $
    \item $ gcd(17, 22) = 1 $
    \item $ gcd(500, 128) = 4 $
\end{itemize}

欧几里得（Euclidean）算法/辗转相除法可以用于计算最大公约数。\\

\mybox{最大公约数}

\begin{lstlisting}[language=Python]
def gcd(a, b):
    while b != 0:
        remainder = a % b
        a = b
        b = remainder
    return a


def euclid_gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)
\end{lstlisting}

\vspace{0.5cm}

\subsection{最小公倍数（LCD, Least Common Multiple）}

两个整数$ a $和$ b $的最小公倍数$ lcm(a, b) $为能够同时被$ a $和$ b $整除的最小整数。\\

例如：

\begin{itemize}
    \item $ lcm(24, 36) = 72 $
    \item $ lcm(17, 22) = 374 $
    \item $ lcm(500, 128) = 16000 $
\end{itemize}

\vspace{0.5cm}

\mybox{最小公倍数}

\begin{lstlisting}[language=Python]
def lcm(a, b):
    return a * b // gcd(a, b)
\end{lstlisting}

\newpage

\section{同余定理}

\subsection{模算数（Modular Arithmetic）}

当$ a \in \mathbb{Z} $、$ M \in \mathbb{Z^+} $，那么将$ a $除以$ m $的余数记为$ a\ \text{mod}\ m $。\\

例如：

\begin{itemize}
    \item 17 mod 5 = 2
    \item 2001 mod 101 = 82
    \item -10 mod 3 = -1
\end{itemize}

\vspace{0.5cm}

\subsection{同余定理（Congruence Theorem）}

当$ a \in \mathbb{Z} $、$ b \in \mathbb{Z} $、$ M \in \mathbb{Z^+} $，如果$ m $能够整除$ a - b $，那么就称$ a $和$ b $对模$ m $同余，记作$ a \equiv b\ (\text{mod}\ m) $。\\

因此，

\vspace{-1cm}

\begin{align}
    a \equiv b\ (\text{mod}\ m) \leftrightarrow a\ \text{mod}\ m \equiv b\ \text{mod}\ m
\end{align}

例如：

\begin{itemize}
    \item $ 17 \equiv 5\ (\text{mod}\ 6) $
    \item $ 17 \equiv 12\ (\text{mod}\ 5) $
    \item $ 24 \equiv 3\ (\text{mod}\ 7) $
\end{itemize}

\vspace{0.5cm}

当$ a \equiv b\ (\text{mod}\ m) $、$ c \equiv d\ (\text{mod}\ m) $，同余定理满足以下性质：

\begin{itemize}
    \item $ a + c \equiv b + d\ (\text{mod}\ m) $
    \item $ ac \equiv bd\ (\text{mod}\ m) $
\end{itemize}

\vspace{0.5cm}

\begin{tcolorbox}
    \mybox{Exercise}\\
    因为$ 7 \equiv 2\ (\text{mod}\ 5) $、$ 11 \equiv 1\ (\text{mod}\ 5) $。\\
    (a) $ 7 + 11\ (\text{mod}\ 5) = 2 + 1 \ (\text{mod}\ 5) = 3 $\\
    (b) $ 7 \cdot 11\ (\text{mod}\ 5) = 2 \cdot 1 \ (\text{mod}\ 5) = 2 $
\end{tcolorbox}

\vspace{0.5cm}

\begin{tcolorbox}
    \mybox{Exercise}\\
    (a) $ 7^{10} \text{mod}\ 5 = 2^{10} \text{mod}\ 5 = 4 $\\
    (b) $ 7^{100} \text{mod}\ 3 = 1^{100} \text{mod}\ 5 = 1 $
\end{tcolorbox}

\newpage

\section{中国余数定理}

\subsection{中国余数定理（CRT, Chinese Remainder Theorem）}

中国余数定理/孙子定理是中国古代求解一次同余式组的算法。在《孙子算经》中有一个叫“物不知数”的问题：\\

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？\\

也就是说，一个整数$ x $除以三余二，除以五余三，除以七余二，求这个整数。\\

该问题可表示为：

\vspace{-1cm}

\begin{align*}
    x \equiv 2\ (\text{mod}\ 3) \\
    x \equiv 3\ (\text{mod}\ 5) \\
    x \equiv 2\ (\text{mod}\ 7)
\end{align*}

或者：

\vspace{-1cm}

\begin{align*}
    x = (2, 3, 2)S(3, 5, 7)
\end{align*}

对于只有两个同余式的问题，可以通过列表的方式直接求解。\\

例如$ x = (2, 4)S(3, 5) $，需要创建一个3行5列的表格，然后以对角线的顺序，从0开始依次填入数字。

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{5mm}{
        \begin{tabular}{|c|c|c|c|c|c|}
            \hline
                       & \textbf{0}           & \textbf{1}           & \textbf{2}             & \textbf{3}             & \textbf{4}             \\
            \hline
            \textbf{0} & \textcolor{red}{0}   & \textcolor{green}{6} & \textcolor{purple}{12} & \textcolor{blue}{3}    & \textcolor{cyan}{9}    \\
            \hline
            \textbf{1} & \textcolor{cyan}{10} & \textcolor{red}{1}   & \textcolor{green}{7}   & \textcolor{purple}{13} & \textcolor{blue}{4}    \\
            \hline
            \textbf{2} & \textcolor{blue}{5}  & \textcolor{cyan}{11} & \textcolor{red}{2}     & \textcolor{green}{8}   & \textcolor{purple}{14} \\
            \hline
        \end{tabular}
    }
\end{table}

找到表格第2行第3列的数值，即$ x = 8 $。\\

同理，用同样的方法可以算出$ (2, 4)S(3, 5) = 14 $。\\

除了列表的方法外，还有一种更加通用的求解同余式组算法。例如对于$ (2, 3, 4)S(3, 5, 13) $这个问题，$ (3, 5, 13) $中两两互素。\\

如果只考虑$ (4)S(13) $，那么可以得出$ x_0 = 4 $。\\

然后再进一步考虑$ (3, 4)S(5, 13) $的情况，那么

\vspace{-1cm}

\begin{align*}
    x_1 & = 4 + 13m = 3\ (\text{mod}\ 5)                              \\
        & = 4 + 13 \times 1 = 17\ \text{（不满足3\ (\text{mod}\ 5)）} \\
        & = 4 + 13 \times 2 = 30\ \text{（不满足3\ (\text{mod}\ 5)）} \\
        & = 4 + 13 \times 3 = 43
\end{align*}

最后在目前的情况下考虑$ (2, 3, 4)S(3, 5, 13) $，那么可以得出

\vspace{-1cm}

\begin{align*}
    x_2 & = 43 + (5 \times 13)m = 2\ (\text{mod}\ 3)                    \\
        & = 43 + 65 \times 1 = 108\ \text{（不满足2\ (\text{mod}\ 3)）} \\
        & = 43 + 65 \times 2= 173
\end{align*}

\newpage

\section{希尔密码}

\subsection{希尔密码（Hill Cipher）}

希尔密码运用基本矩阵运算来对明文加密，它将字母$ A \sim Z $用$ 0 \sim 25 $表示。因此一段长度为$ n $的明文可以表示成一个包含$ n $个元素的明文矩阵。将这个明文矩阵与密钥矩阵相乘，得到的结果经过模26后就是密文。\\

例如密钥矩阵为：

\[
    \begin{bmatrix}
        1  & 2 & 3 \\
        4  & 5 & 6 \\
        11 & 9 & 8
    \end{bmatrix}
\]

\vspace{0.5cm}

明文为$ ABC = (0, 1, 2) $。\\

密文可以通过矩阵乘法得到：

$$
    \begin{bmatrix}
        1  & 2 & 3 \\
        4  & 5 & 6 \\
        11 & 9 & 8
    \end{bmatrix}
    \times
    \begin{bmatrix}
        0 \\
        1 \\
        2
    \end{bmatrix}
    =
    \begin{bmatrix}
        8  \\
        17 \\
        0
    \end{bmatrix}
    \ (\text{mod}\ 26) = IRA
$$

\vspace{0.5cm}

希尔密码的好处在于，如果明文中的一个字母发生变化，密文中所有的字母都会受到影响。\\

例如当明文为$ BBC = {1, 1, 2} $时：

$$
    \begin{bmatrix}
        1  & 2 & 3 \\
        4  & 5 & 6 \\
        11 & 9 & 8
    \end{bmatrix}
    \times
    \begin{bmatrix}
        1 \\
        1 \\
        2
    \end{bmatrix}
    =
    \begin{bmatrix}
        9  \\
        21 \\
        10
    \end{bmatrix}
    \ (\text{mod}\ 26) = JVK\\
$$

\vspace{0.5cm}

\subsection{解密}

例如已知一个模5的密钥矩阵：

\[
    K =
    \begin{bmatrix}
        1 & 0 & 1 \\
        1 & 2 & 1 \\
        3 & 1 & 4
    \end{bmatrix}
\]

\vspace{0.5cm}

和一个待破解的密文：

\[
    C =
    \begin{bmatrix}
        A & F & S \\
        A & S & E \\
        F & A & E
    \end{bmatrix}
\]

\vspace{0.5cm}

以及字母与数字的对应关系：

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{5mm}{
        \begin{tabular}{|c|c|c|c|c|}
            \hline
            0 & 1 & 2 & 3 & 4 \\
            \hline
            A & E & F & S & T \\
            \hline
        \end{tabular}
    }
\end{table}

希尔密码的解密过程如下：

\begin{enumerate}
    \item 计算密钥矩阵$ K $的模逆矩阵$ K^{-1} $
    \item 计算$ K^{-1} \times C $
    \item 将结果转换为字母
\end{enumerate}

利用初等行变换，可以计算$ K $的模逆矩阵$ K^{-1} $。注意在矩阵的运算过程中，始终要保证模5的操作，如$ 0 - 1 = 4 $。

\begin{alignat*}{2}
    \begin{sysmatrix}{ccc|ccc}
        1 & 0 & 1 & 1 & 0 & 0 \\
        1 & 2 & 1 & 0 & 1 & 0 \\
        3 & 1 & 4 & 0 & 0 & 1
    \end{sysmatrix}
     & \!\begin{aligned}
         & \ro{R_2 = R_2 - R_1}  \\
         & \ro{R_3 = R_3 - 3R_1}
    \end{aligned}
    \begin{sysmatrix}{ccc|ccc}
        1 & 0 & 1 & 1 & 0 & 0 \\
        0 & 2 & 0 & 4 & 1 & 0 \\
        0 & 1 & 1 & 2 & 0 & 1
    \end{sysmatrix}
    \\
     & \!\begin{aligned}
         & \ro{R_2 = R_2 - R_3} \\
         & \ro{R_3 = R_3 - R2}
    \end{aligned}
    \begin{sysmatrix}{ccc|ccc}
        1 & 0 & 1 & 1 & 0 & 0 \\
        0 & 1 & 4 & 2 & 1 & 4 \\
        0 & 0 & 2 & 0 & 4 & 2
    \end{sysmatrix}
    \\
     & \!\begin{aligned}
         & \ro{R_3 = R_3 / 2}
    \end{aligned}
    \begin{sysmatrix}{ccc|ccc}
        1 & 0 & 1 & 1 & 0 & 0 \\
        0 & 1 & 4 & 2 & 1 & 4 \\
        0 & 0 & 1 & 0 & 2 & 1
    \end{sysmatrix}
    \\
     & \!\begin{aligned}
         & \ro{R_1 = R_1 - R_3} \\
         & \ro{R_2 = R_2 - 4R3}
    \end{aligned}
    \begin{sysmatrix}{ccc|ccc}
        1 & 0 & 0 & 1 & 3 & 4 \\
        0 & 1 & 0 & 2 & 3 & 0 \\
        0 & 0 & 1 & 0 & 2 & 1
    \end{sysmatrix}
\end{alignat*}

\begin{align*}
    K^{-1} \times C & =
    \begin{bmatrix}
        1 & 3 & 4 \\
        2 & 3 & 0 \\
        0 & 2 & 1
    \end{bmatrix}
    \begin{bmatrix}
        A & F & S \\
        A & S & E \\
        F & A & E
    \end{bmatrix}
    \\
                    & =
    \begin{bmatrix}
        1 & 3 & 4 \\
        2 & 3 & 0 \\
        0 & 2 & 1
    \end{bmatrix}
    \begin{bmatrix}
        0 & 2 & 3 \\
        0 & 3 & 1 \\
        2 & 0 & 1
    \end{bmatrix}
    \\
                    & =
    \begin{bmatrix}
        3 & 1 & 0 \\
        0 & 3 & 4 \\
        2 & 1 & 3
    \end{bmatrix}
    \\
                    & =
    \begin{bmatrix}
        S & E & A \\
        A & S & T \\
        F & E & S
    \end{bmatrix}
\end{align*}

\vspace{0.5cm}

最终得到明文为SAFE SEATS。

\newpage